1. Введение С тех давних пор как я узнал что есть CLIPPER, меня неизменно притягивало узнать как построена его индексная система. Меня поражала мощь, гибкость и главное скорость поисковой работы в огромных, по моим понятиям, базах данных. Я приходил в восторг от реализации отношений между базами по индексным ключам, фактически моментальной сортировки необъятных объемов информации по необходимым мне полям, поддержки одновременно нескольких порядков сортировки в интерактивных режимах работы. Это было здорово, и это было давно. Теперь я более чем реально представляю себе как это все работает, меня это уже не удивляет, что отчасти печально. Но как бы там ни было я хочу поделиться своими соображениями по этому поводу. 2. Теоретическая часть 2.1 Основные понятия Прежде всего введу понятия ключа. Здесь и далее под ключом я буду понимать совокупность из одного или нескольких атрибутов, которые могут идентифицировать каждую сущность множества. Поясню по русски. Множеством может быть, например, множество записей некоторой базы данных. Ключом может быть любое поле базы, совокупность полей, часть поля, часть совокупности полей, любая функция как от любого поля так и от совокупности любых полей, любая совокупность от любых функций и т.д. - то есть все что угодно, единственное требование, чтобы это "что угодно" соотносилось с конкретной записью базы данных. В теории баз данных ключи подразделяют на суперключи, ключи-кандидаты и первичные ключи. Но это сейчас Вас интересовать не должно, потому, что суть в однозначном соотношении ключ-данные. Второе понятие, которым я буду пользоваться, - это понятие индекса. Под индексом понимается множество всех ключей. Из определения понятно, что индекс однозначно определяет данные, на которых построены ключи. Таким образом перемещение по индексу определяет перемещение по данным. Основной темой для дальнейшего разговора будет чисто техническая реализация индекса. Простейшая структура "держащая" индекс - это всего навсего файл в котором последовательно перечислены все ключи со ссылками на соответствующие данные: -------------------- --¬ ¦• • • • • • • • • • ... ¦ L+-+-+--------------- --- ----- ¦ L---¬ Ключ1 Ключ2 Ключ3 ... (рис.1) И на интуитивном уровне понятно, что подобная организация не может служить серьезным основанием для работы драйвера индексной системы. Я даже не буду пытаться перечислять недостатки подобного подхода, поскольку уверен, что они Вам известны не хуже меня. Я сделаю другое, и настоятельно советую Вам внимательно следить за тем, что я сделаю. Пусть ключей в индексе M, а m некоторое число которое, допустим, значительно меньше M. Разделим всю совокупность ключей на равные части по m+1 ключей: -------¬ -------¬ -------¬ -------¬ ¦••••••¦ ¦••••••¦ ¦••••••¦ ... ¦••••••¦ L------- L------- L------- L------- m+1 m+1 m+1 m+1 (рис.2) Получим K0 = M/(m+1) страниц по (m+1) ключу. Вытащим каждый (m+1)-ый ключ из каждой страницы, наделим его ссылкой на его родную страницу, и организуем из них структуру, подобную структуре на (рис.1) из K0 ключей: --------------------- --¬ ¦• • • • • • • • • • • • • • • • ... • •¦ L+-+-+-+------------- -+-+- ¦ ¦ ¦ L----- ... K0 ... --------------- ¦ --- ¦ L------¬ ------------------- ------+¬ -+-----¬ -+-----¬ ------+¬ ¦••••••¦ ¦••••••¦ ¦••••••¦ ... ¦••••••¦ L------- L------- L------- L------- m m m m (рис.3) Разделим полученную совокупность из K0 ключей на K1 = K0/(m+1) страниц по (m+1) ключу. Вытащим каждый (m+1) ключ на следующий уровень, и так до тех пор, пока в конечной линейной структуре не окажется ключей меньше или равно m. Получим приблизительно следующие: ------¬ ¦• • •¦ L+-+-+- ¦ ¦ ¦ ---- ¦ L--¬ -----+¬---+--¬-+----¬ ¦• • •¦¦• • •¦¦• • •¦ L+-+-+-L+-+-+-L+-+-+- ------------------- ¦ ¦ ¦ ¦ ¦ ¦ ¦ L------------------¬ ¦ --------------- ¦ ¦ ¦ ¦ ¦ L-------------¬ ¦ ¦ ¦ ---------- ¦ ¦ ¦ L---------¬ ¦ ¦ ¦ ¦ ¦ ----- ¦ L----¬ ¦ ¦ ¦ --+---¬-+----¬-+----¬--+---¬-+----¬-+----¬--+---¬-+----¬-+----¬ ¦• • •¦¦• • •¦¦• • •¦¦• • •¦¦• • •¦¦• • •¦¦• • •¦¦• • •¦¦• • •¦ L------L------L------L------L------L------L------L------L------ (рис.4) Для тех, кто ни с чем подобным до сих пор не сталкивался охотно объясню - господа, перед вами В-дерево. В принципе индекс может хранить ключи как в сортированном виде, так и в любом другом порядке. Практический интерес, естественно, представляют сортированные индексы, потому что: 1) Индекс упорядочен по ключу,; 2) В упорядоченной информации ЗНАЧИТЕЛЬНО легче производить поиск.; Упорядоченное В-дерево обладает целым рядом уникальных особенностей, что и делает его использование в индексной системе практически единственно приемлемым. Помимо того, что дерево "держит" ключи, ему необходимо "держать" также некоторую информацию, необходимую для организации самого дерева. Эта информация в совокупности с ключом называется ПУНКТОМ (ITEM). Страницы у дерева могут быть полностью заполнены, или заполнены не менее чем до половины. В первом случае дерево называется плотноупакованным во втором разрешенным. 2.2 Важнейшие характеристики В-дерева m - Количество ключей на странице,; n = m/2 - Половина ключей на странице,; L - Количество уровней В-дерева,; M - Количество ключей в дереве,; K - Количество страниц всего в дереве,; K(l) - Количество страниц уровня l,; S - Длина страницы,; KS - Длина ключа,; KI - Длина ITEM,; SS - Длина индекса в целом. Характеристика длина страницы (S) устанавливается как правило из субъективных предпосылок по приблезительному количеству ключей на странице, длине ключа и способностей магнитных накопителей, на которых это все должно храниться. Для драйвера DBFNTX длина страницы установлена в S = 1024 байт (1K). Длина ключа и длина ITEM вычисляется при конкретном построении конкретного индекса с конкретным ключевым выражением. Очевидно, что количество ключей в дереве будет равно числу записей в базе данных. Количество ключей на странице и половина ключей на странице вычисляется просто делением длины страницы на длину ITEM. Приведу известное соотношение между количеством ключей в дереве, количеством ключей на странице и количеством уровней в В-дереве: L --- l M = > m ; (1) --- l = 1 Это значит, что если ключей на странице 10 и в дереве 1 уровень, то ключей в дереве - 10. Это и понятно, все дерево состоит из одной страницы. При двух уровнях имеем: 10+10*10 = 110 ; При трех: 10+10*10+10*10*10 = 1110; При 10 уровнях получаем 11`111`111`110 - более чем 11 миллиардов ключей. Чтобы определить приблизительно количество уровней в дереве, необходимых для поддержки индекса из M ключей можно воспользоваться формулой: L = log M ; (2) (m+1) И действительно: log 11`111`111`110 = 10 (с округлением до большего целого); 11 На нулевом уровне дерева находится единственная страница, которая называется корневой страницей. Очевидно, что количество страниц второго уровня в точности равно количеству ключей корневой страницы, количество страниц третьего уровня равно количеству ключей второго уровня, и т.д.: K(0) = 1 ; (3) K(1) = m ; (4) K(2) = m*m ; (5) l K(l) = m ; (6) (L-1) K(L-1) = m ; (7) Таким образом общее количество страниц в дереве: L-1 --- l K = > m ; (8) --- l = 0 Посчитаем сколько необходимо страниц для хранения 11`111`111`110 ключей. Предположим, что длина ключа 12 байт, длина ITEM в драйвере DBFNTX на 8 байт больше длины ключа, т.е. 20 байт, так как мы приняли m = 10, то длина страницы будет 20*10=200 байт, количество страниц по формуле (8) K = 2593742460, посему имеем: SS = K*200 = 518`748`492`000 байт = 506`590`324.22 Kd = 494`717.11 Mb Все выше описанные формулы справедливы для плотноупакованного дерева. Для разрешенного дерева следует заменить m на n. 2.3 Сортированное В-дерево. Как я уже упоминал ранее В-дерево может хранить ключи как в упорядоченном виде, так и в любом другом. Например, просто в порядке их следования в базе. Так чем же отличается сортированное дерево от несортированного. Проведем операцию, описанную в п.2.1, но с одним условием - начальное множество всех ключей упорядочено по возрастанию значения ключа. Тогда при вытаскивании каждого (m+1) ключа на следующий уровень мы получим картину, когда : 1) На каждой странице нижнего уровня ключи упорядочены,; 2) Каждый (m+1) ключ является старшим в своей странице,; 3) Все вытащенные (m+1) ключей на верхний уровень упорядочены. Продолжая процесс п.2.1 мы получим сортированное дерево, в котором любой ключ удовлетворяет этим трем пунктам. Отсюда следует один важный вывод: В упорядоченном по возрастанию ключей В-дереве любой взятый произвольно ключ будет старше всех ключей ниже и левее его в дереве. 2.4 Построение В-дерева. Построение дерева, приведенное в п.2.1 является чисто академическим примером необходимым для понимания сути описываемой структуры. В реальной ситуации этот метод естественно не приемлем. Для построения дерева можно использовать два основных алгоритма, которые я обозвал как "Сквозной массив" и метод деления страниц. Названия методов чисто условны и являются сугубо моими фантазиями. Это просто следствие того, что я не нашел в Москве литературы, освещающей данную тему. 2.4.1 Метод "Сквозной массив". Является наиболее быстрым методом получения В-дерева. Основан на использовании массива страниц дерева по одной с каждого уровня - сквозной массив. В начале работы массив имеет один элемент с одной страницей. После заполнения страницы ключами она отправляется в буфер обмена с диском (либо сразу на диск, если Вам не жалко время), в массив добавляется страница следующего уровня, в которую заноситься ключ со ссылкой на сформированную страницу, а страница массива нижнего уровня обнуляется, и в нее опять заносятся ключи до заполнения. Процесс повторяется до заполнения верхней страницы. С заполненой верхней страницей происходит тоже самое, что происходило с первой страницей - она отправляется в буфер, обнуляется, организуется третий уровень, куда записывается следующий ключ со ссылкой на сформированную страницу. Продолжает заполняться нижняя страница и т.д. пока не иссякнет источник ключей. Схематично это можно показать следующим образом: Буфер обмена с диском (DTA) ----------------¬ ¦--¬--¬--¬--¬--¬¦ Сквозной массив ¦¦1¦¦2¦¦3¦¦4¦¦5¦¦ ¦ ¦L--L--L--L--L--¦ --------¬ ¦ ¦--¬ ¦ ¦------¬¦ ¦ ¦¦6¦ ... ¦ ---------++• ¦+-+ ¦L-- ¦ ¦ ¦L------¦ ¦ ¦ ¦ ¦ L-------- ¦ L---------------- ¦ --------¬ ¦ ----+-¬ ¦------¬¦ ¦ ¦• • •¦ ---++• • ¦+-+ L+-+-+- ¦ ¦L--+---¦ ¦ -------------------------- ¦ ¦4 ¦ L---+---- ¦ ¦ -------------------- ¦ ¦ ¦ ¦ ¦ ¦ -------------- ¦ ¦ ¦ ¦ ¦ ¦ ----------- ¦ ¦ ¦ ¦ ¦ ¦ ---------- ¦ ¦ ¦ ¦ ¦ ¦ --------¬ ¦ ----+-¬ ----+-¬ ----+-¬ ----+-¬ ----+-¬ ¦------¬¦ ¦ ¦• • •¦ ¦• • •¦ ¦• • •¦ ¦• • •¦ ¦• • •¦ ¦¦• • ¦+-- L------ L------ L------ L------ L------ ¦L------¦ 1 2 3 5 6 L-------- (рис.5) Цифрами помечены уже заполненые страницы в той последовательности, в какой они попадают в DTA. В конечном итоге сквозной массив имеет столько элементов, сколько уровней в В-дереве, и все, что останется сделать методу - это запомнить на диске сам массив с оставшимися ключами и связать между собой его страницы. При использовании метода "Сквозной массив" дерево получается с плотноупакованными страницами, и, как я уже отмечал, происходит это очень быстро. Это есть два существенных преимущества метода. К недостаткам можно отнести тот печальный факт, что сортированное дерево данным способом можно получить только в одном единственном случае - когда ключи, последовательно поступающие в процесс, уже отсортированны. 2.4.2 Метод деления по предпоследнему пункту. В этом методе осуществляется рекурсивный проход по дереву от корня до последнего листа в прямом смысле, т.е.: берем корневую страницу, скачем на последний ключ, если у этого ключа есть ссылка на страницу следующего уровня переходим на нее и повторяем с ней описанную процедуру. Так до тех пор, пока не наткнемся на пустую ссылку, что означает конец индекса. Своеобразный GO BUTTOM по В-дереву. Добавляем в последнюю страницу ключ и проверяем, не заполнена ли она. Если заполнена то (тут самое главное!) мы извлекаем из этой страницы предпоследний ключ, а саму страницу делим на две. В одну пихаем все, что слева, а во вторую единственный последний ключ. На этом на текущем уровне процесс вделывания ключа завершен, возвращаемся к предыдущему уровню, на котором пытаемся вделать извлеченный предпоследний ключ со ссылкой на только что сделанную страницу. Процесс либо завершается, если для ключа есть место, либо продолжается, если для него места нет. Так доходим до корневой страницы. Допустим, что мы и ее разделили на две, тогда куда девать оставшийся предпоследний ключ с корневой страницы? В этом случае организуется новая страница, которой присваивается статус корневой, в нее пихается этот ключ со ссылкой на старую корневую страницу. На этом процедура добавления ключа завершается. Схема работы алгоритма по шагам: 1.------¬ 2.------¬ 3. ------¬ 4. ------¬ ¦ ¦ ¦• • •¦ ¦• ¦ ¦• ¦ L------ L------ L++----3 L++----3 1 1 ¦L---¬ ¦L--¬ ----+-¬ -+----¬ ----+-¬-+----¬ ¦• ¦ ¦• ¦ ¦• ¦¦• • •¦ L------ L------ L------L------ 1 2 1 2 5. ------¬ 6. ------¬ ¦• • ¦ ¦• • ¦ L+-+-+-3 L+-+-+-3 ¦ ¦ L------¬ ¦ ¦ L------¬ ¦ L-¬ ¦ ¦ L-¬ ¦ ----+-¬-+----¬-+----¬ ----+-¬-+----¬-+----¬ ¦• ¦¦• ¦¦• ¦ ¦• ¦¦• ¦¦• • •¦ L------L------L------ L------L------L------ 1 2 4 1 2 4 7. ------¬ ¦• ¦ L++----7 ¦L--------¬ -+----¬ -+----¬ ¦• ¦ ¦• ¦ L++----3 L++----6 ¦¦ ¦L----------¬ ¦L--¬ L¬ ¦ ----+-¬-+----¬-+----¬ ----+-¬ ¦• ¦¦• ¦¦• ¦ ¦• ¦ L------L------L------ L------ 1 2 4 5 (рис.6) Страницы пронумерованы в порядке их создания. При использовании метода деления страниц предпоследним элементом дерево получается плотноупакованным, за исключением двух ключей на каждой разделенной странице. Если правильно организована буферизация страниц то алгоритм работает достаточно быстро, хотя и по медленнее "Сквозного массива". В отличие от "Сквозного массива" возможна адаптивная сортировка ключей в процессе добавления, вследствии чего получается отсортированное дерево. Но подобная сортировка крайне не эффективна. 2.4.3 Метод половинного деления. Отличается от предыдущего метода только тем, что в качестве делителя страницы используется не предпоследний ключ, а ключ в середине страницы, в следствии чего получается некий запас для дальнейшего заполнения этой страницы. Дерево получается разрешенным, работает это ,как правило, в два раза медленнее предыдущего метода, поэтому практически не используется. 2.4.4 Метод половинного деления с сортировкой. Есть одна особенность, делаюшая метод основным для интерактивного заполнения В-дерева. Особенность в том, что метод позволяет поддерживать порядок в дереве сколько бы ключей мы в него не добавляли. Фактически метод половинного деления плюс сортировка работает, когда Вы в tBrowse редактируете базу данных с подключенным индексом. В методе деления предпоследним элементом чтобы добавить ключ использовалось подобие GO BOTTOM для нахождения местоположения ключа. Иными словами, мы всегда добавляли ключ в конец индекса. При методе половинного деления с сортировкой вместо GO BOTTOM используется подобие SEEK по В-дереву, и мы именно на это место вделываем ключ и при необходимости делим страницу пополам, передавая средний ключ на верхние структуры дерева для того, чтобы там с ним сделать тоже самое, поддерживая постоянный порядок в индексе. 2.5 Перемещение по дереву. Различают прямой и обратный порядок обхода дерева. Прямой порядок нужен для прохождения В-дерева от начала до конца, обратный порядок соответственно - от конца до начала. 2.5.1 Прямой порядок. Начинается все с корневой страницы. Прочитав страницу определяем в ней первый ключ. Не выдавая его в качестве выходной информации, смотрим, нет ли у данного ключа ссылок на более низкие страницы. Если есть прыгаем туда, и так до тех, пока не упремся в начало индекса. Тогда, двигаясь по странице выдаем ключи. Вернувшись на страницу более высокого уровня выдаем текущий ключ и двигаемся вправо. Все повторяется до конца индекса. Основная суть в том, что вначале проверка на наличие более низкого уровня, потом ключ. 2.5.1 Обратный порядок. Основная суть в том, что вначале ключ , потом проверка на наличие более низкого уровня. В остальном тоже самое что и прямой порядок. 2.6 Поиск по дереву. За что люблю сортированное дерево, так это за то, что искать в нем нужный ключ просто песня. Все, как и раньше, начинается с корневой страницы. Устанавливаем на ней первый ключ, который больше искомого, или равен ему. Это значит, что все ветки дерева, до первого большего ключа исключаются из процедуры поиска за полной ненадобностью (а это может быть очень не кисло). Если у найденого большего ключа есть ссылка на дочерние страницы, прыгаем туда. Там делаем тоже самое и т.д. пока не найдем то что надо. Из описанной процедуры становиться ясно, что для того чтобы что-то найти в дереве нужно перебрать количество страниц, равное количеству уровней, и сделать сравнений в среднем в половину ключей на каждой странице. Если обратиться к примеру, приведенному мной ранее, с деревом в 11`111`111`110 ключей, то окажется, что для того чтобы в нем найти нужный ключ, надо перебрать 10 страниц и сделать приблизительно 50 сравнений !!!! Не знаю как Вам, господа, но мне это сразу показалось гениальным. 2.7 Сортировка неупорядоченного дерева. Честно сказать я понятия не имею как сортировать неупорядоченное В-дерево. Единственное соображение которое у меня пока есть следующее. Если отсортировать последовательно по отдельности цепочки от корня к конечным страницам и сами конечные страницы, то мы соберем в корне дерева самые старшие ключи, но что с ними делать потом... затрудняюсь ответить. 2.8 Псевдо ключ, буферизация страниц, предварительная сортировка. В этом разделе попытаюсь объяснить некоторые тонкости, без которых, однако, врядли что будет работать. Первая тонкость в том, что на каждой странице В-дерева необходим специальный псевдо ключ, который, собственно, как ключ не значим. А нужен только для того, чтобы указывать на страницу, ключи которй, старше любого ключа текуший страницы. ----------------------------------------------------- ¦ Страница ¦ Item1 Item2 Item3 ItemN ¦ ---------¬---------¬---------¬ ---------¬ ¦ ¦Значимы馦Значимы馦Значимый¦ ¦Псевдо ¦ ¦ ¦ ключ ¦¦ ключ ¦¦ ключ ¦ ¦ ключ ¦ ¦ ¦ ¦¦ ¦¦ ¦ ... ¦ ¦ ¦ ¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦ +--------++--------++--------+ +--------+ ¦ ¦ Запись ¦¦ Запись ¦¦ Запись ¦ ¦ ¦ ¦ +--------++--------++--------+ +--------+ ¦ ¦Мл.стр. ¦¦Мл.стр. ¦¦Мл.стр. ¦ ¦Ст.стр. ¦ ¦ L---+-----L---+-----L---+----- L---+----- ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦     (рис.7) Вторая тонкость - это буферизация страниц во время работы алгоритмов. Чем грамотней организована буферизация, тем быстрее работают программы. В своей библиотеке я применил способ, заключающейся в подсчете частот использования страниц. Наиболее используемые страницы постоянно находяться в памяти и их не надо считывать с диска. Для наилучшего использования памяти я объеденил страницы в блоки и подсчитывал частоты использования блоков. Как выяснилось оба способа не достаточно эффективны. Более приемлемым вариантом было бы сохранение в памяти пути до некоторого ключа, обрабатываемого последним, или целого стека таких путей. Кортоко о предварительной сортировке. Она необходима при методе половинного деления с сортировкой. Допустим мы добавили в дерево ключ и запомнили путь до него в памяти. Допустим мы хотим добавить второй, и нам не известно заранее в какую часть дерева он попадет, но очень хотелось бы, чтобы при добавлении он прошел как можно более долго по уже сохраненному пути. В этом случае не потребуется перегружать страницы в памити, поэтому сортировка должна идти значительно быстрее. Именно для этого нужна предварительная сортировка буфера ключей, прежде чем их отправлять в дерево. 3. Реализация индексов в драйвере DBFNTX Индексный файл драйвера DBFNTX есть вполне физическая реализация теории модифицированных В-деревьев. Файл состоит из 1K страниц, первая страница представляет собой заголовок индекса. Структура заголовка характеризуется следующей структурой языка C: // // Заголовок индексного файла (первая страница любого индекса) // typedef struct{ unsigned sign; //2 unsigned version; //2 long root; //4 long next_page; //4 unsigned item_size; //2 unsigned key_size; //2 unsigned key_dec; //2 unsigned max_item; //2 unsigned half_page; //2 char key_expr[MAX_KEY]; //1 char unique; //1 char Rest[1000]; //1000 }NTX_HEADER; // 1024 (смотри файл dbf_ntx.h) sign - Двухбайтовое поле со значением 0x03, указывающие, что файл является файлом dBase/Clipper. version - Поле, используемое CLIPPER для определения версии индексной системы. root - Смещение в файле первой индексной страницы. next_page - Смещение в файле NTX первой пустой страницы. Используется для удаления ITEM из индекса. Первая пустая страница может содержать в начале не пустые 4 байта - указатель на следующую пустую страницу. Нулевой указатель завершает список. dBase не обрабатывает свободный список, поэтому она не использует страницы повторно. item_size - Размер пункта. Это размер ключа плюс два длинных целых. key_size - Размер ключа. dBase хранит в индексе только символьные ключи. Типы N, L, D преобразуются к символьному виду по определенным правилам. key_dec - Точность ключа для числовых ключей. max_item - Максимальное количество ключей, которое может вместить индексная страница. half_page - Максимальное количество ключей, которое может вместить индексная страница, деленная пополам. Очень важная величина, она равна менимальному колличеству ключей, которое должно быть на странице. key_expr[MAX_KEY] - Фактическое выражение по которому был построен индекс. Это оканчивающаяся на NIL строка, с максимальной длинной 256. unique - Булевская величина, содержащая состояние флага уникальности при создании индекса. Rest[1000] - Заполннитель до 1K. Структура заголовка индекса приведена для CLIPPER 5.01 и ниже. Начиная с версии CLIPPER 5.2 в заголовок добавлено поле, характеризующее условие индексации. Все остальные страницы индекса, кроме неиспользуемых, содержат ITEM-ы. В ITEM-ах храниться информация о ключе, номере записи базы данных - источнике ключа и о странице, содержащей ITEM-ы с меньшими ключами. В терминах язака С это выглядет следующем образом: // // Структура, описывающая один ITEM // typedef struct{ long page; //Смещение в файле NTX дочерней страницы. long rec_no; //Номер записи в базе данных. char key; //Начало символьного массива с ключем. }NTX_ITEM; Поле key фактически является началом массива длинной key_size с типом char. Это и есть ключ индекса. Физически ITEM-ы на странице могут распологаться в любом порядке. Логический порядок ITEM определят массив ссылок на них в самом начале любой индексной страницы. Самые первые два байта страницы определяют сколько всего ITEM на странице (на самом деле их всегда на 1 больше, если учесть последний псевдо-ITEM). ----------------------------------------------------- ¦ Страница ¦ ¦ Count Массив ref ¦ ¦¦ ----¬ ----¬ ----¬ ----¬ ¦ ¦¦ L-T-- L-T-- L-T-- L-T-- ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ Item1 ¦ Item2 ¦ Item3 ¦ ItemN ¦ ¦ ------+--¬------+--¬------+--¬ ------+--¬ ¦ ¦Значимы馦Значимы馦Значимый¦ ¦Псевдо ¦ ¦ ¦ ключ ¦¦ ключ ¦¦ ключ ¦ ¦ ключ ¦ ¦ ¦ ¦¦ ¦¦ ¦ ... ¦ ¦ ¦ ¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦ +--------++--------++--------+ +--------+ ¦ ¦ Запись ¦¦ Запись ¦¦ Запись ¦ ¦ ¦ ¦ +--------++--------++--------+ +--------+ ¦ ¦Мл.стр. ¦¦Мл.стр. ¦¦Мл.стр. ¦ ¦Ст.стр. ¦ ¦ L---+-----L---+-----L---+----- L---+----- ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦     (рис.8) Таким образом страница начинается со структуры: // // Структура с которой начинаются индексные страницы // typedef struct{ unsigned count; //Счетчик количества ITEM на странице. unsigned ref; //Начало массива ссылок на ITEM-ы. }NTX_BUFFER; Приведу очевидное уравнение, связывающее максимальное количество ITEM на странице с длинной ключа: item_size = key_size+8 ; (9) NTX_PAGE = (max_item+1)*item_size+(max_item+1)*2+2 ; (10) где NTX_PAGE - длинна индексной страницы (1K). От куда находим: max_item = (NTX_PAGE-item_size-4)/(item_size+2) ; (11) Выражение (11) позволяет найти максимальное количество ITEM на странице по длинне ключа индексирования. Очевидно, что half_page = max_item/2 ; (12) Схематично весь индексный файл драйвера DBF_NTX можно представить в следующем виде: ---------------------------------------------¬ ¦ NTX_HEADER ¦ ¦ root -------------------------------------+--¬ L--------------------------------------------- ¦ . . . . .  ----¬¦ --------------------------------------------¬ ¦¦ ¦г=======¬ ref ¦ ¦¦ ¦¦ count ¦ -¬-¬-¬ -¬ ... ¦ ¦¦ ¦L=======- L+L+L+ ... L+  ¦ ¦¦ ¦ ¦ ¦ ¦ --+--T-------T-----¬ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ page¦ rec_no¦ key ¦ ¦ ¦¦ ¦ ¦ ¦ ¦ L-----+-------+------ ¦ ¦¦ ¦    ... ¦ ¦¦ ¦ ¦ ¦ ¦  ¦ ¦¦ ¦ ¦ ¦ +--+--T-------T-----¬ ¦ ¦¦ ¦ ¦ ¦ ¦ page¦ rec_no¦ key ¦ ¦ ¦¦ ¦ ¦ ¦ L-----+-------+------ ¦ ¦¦ ¦ ¦ ¦ ... ¦ ¦¦ ¦ ¦ ¦  ¦ ¦¦ ¦ ¦ +--+--T-------T-----¬ ¦ ¦¦ ¦ ¦ ¦ page¦ rec_no¦ key ¦ ¦ ¦¦ ¦ ¦ L-----+-------+------ ¦ ¦¦ ¦ ¦ ... ¦ ¦¦ ¦ ¦  ¦ ¦¦ ¦ +--+--T-------T-----¬ ¦ ¦¦ ¦ ¦ page¦ rec_no¦ key ¦ ¦ ¦¦ ¦ L-----+-------+------ ¦ ¦¦ L--------------------------------------------- ¦¦ . . . . . ¦ ----+- --------------------------------------------¬ ¦ ¦г=======¬ ref ¦ ¦ ¦¦ count ¦ -¬-¬-¬ -¬ ¦ ¦ ¦L=======- L+L+L+ ... L+ ¦ ¦ ¦ ¦ ¦ ¦  ------------------+-- ¦ ¦ ¦ ¦ +--+--T-------T-----¬ ¦ ¦ ¦ ¦ ¦ ¦ page¦ rec_no¦ key ¦ ¦ ¦ ¦ ¦ ¦ L-----+-------+------ ¦ ¦ ¦ ¦ ¦ ¦ ¦    ¦ ¦ ¦ ¦ ¦ -------------------------+-¬ ¦ ¦ ¦ ¦  ¦ ¦ ¦ ¦ ¦ +--+--T-------T-----¬ ¦ ¦ ¦ ¦ ¦ ¦ page¦ rec_no¦ key ¦ ¦ ¦ ¦ ¦ ¦ L-----+-------+------ ¦ ¦ ¦ ¦ ¦ ... ¦ ¦ ¦ ¦ ¦  ¦ ¦ ¦ ¦ +--+--T-------T-----¬ ¦ ¦ ¦ ¦ ¦ page¦ rec_no¦ key ¦ ¦ ¦ ¦ ¦ L-----+-------+------ ¦ ¦ ¦ ¦ ... ¦ ¦ ¦ ¦  ¦ ¦ ¦ +--+--T-------T-----¬ ¦ ¦ ¦ ¦ page¦ rec_no¦ key ¦ ¦ ¦ ¦ L-----+-------+------ ¦ ¦ L--------------------------------------------- ¦ . . . . . ----- --------------------------------------------¬ ¦г=======¬ ref ¦ ¦¦ count ¦ -¬-¬-¬ -¬ ... ¦ ¦L=======- L+L+L+ ... L+  ¦ ¦ ¦ ¦ ¦ --+--T-------T-----¬ ¦ ¦ ¦ ¦ ¦ ¦ page¦ rec_no¦ key ¦ ¦ ¦    L-----+-------+------ ¦ ¦ ¦ ¦ ¦ ... ¦ ¦ ¦ ¦ ¦  ¦ ¦ ¦ ¦ +--+--T-------T-----¬ ¦ ¦ ¦ ¦ ¦ page¦ rec_no¦ key ¦ ¦ ¦ ¦ ¦ L-----+-------+------ ¦ ¦ ¦ ¦ ... ¦ ¦ ¦ ¦  ¦ ¦ ¦ +--+--T-------T-----¬ ¦ ¦ ¦ ¦ page¦ rec_no¦ key ¦ ¦ ¦ ¦ L-----+-------+------ ¦ ¦ ¦ ... ¦ ¦ ¦  ¦ ¦ +--+--T-------T-----¬ ¦ ¦ ¦ page¦ rec_no¦ key ¦ ¦ ¦ L-----+-------+------ ¦ L--------------------------------------------- (рис.9) Обратите внимание, пожалуйста, на то, что, чтобы вделать ITEM в середину страницы совсем не обязательно двигать ITEM-ы. Достаточно подвинуть массив ref с соответствующей позиции. Это тоже весьма экономит время, поскольку ключи могут быть достаточно длинными. 4. Примеры Все примеры работы с индексным файлом драйвера DBFNTX сосредоточены в моей маленькой библиотеке NTX_UT.LIB которая находиться в одноименной директории. Библиотечные модули включают в себя: ------------T----------------------------T-----------------------------¬ ¦Объектный ¦Исходный текст ¦Описание ¦ ¦модуль ¦ ¦ ¦ +-----------+----------------------------+-----------------------------+ ¦FNtx.obj ¦FNtx.c dbf_ntx.h ¦Индексация базы данных ¦ ¦bufntx.obj ¦bufntx.c dbf_ntx.h ¦Буферизация индексного файла ¦ ¦SbNtx.obj ¦SbNtx.c dbf_ntx.h ¦Построение ПодИндекса вар.2 ¦ ¦SubNtx.obj ¦SubNtx.c dbf_ntx.h SubUt.h¦Построение ПодИндекса вар.1 ¦ ¦SubUt.obj ¦SubUt.c dbf_ntx.h SubUt.h¦Сервис для SubNtx.obj ¦ ¦NtxAn.obj ¦NtxAn.c dbf_ntx.h ¦Разбор индексного файла ¦ ¦NtxLoop.obj¦NtxLoop.c dbf_ntx.h ¦Цикл по индексу ¦ ¦LogRec.obj ¦LogRec.c dbf_ntx.h ¦Логический номер по индексу ¦ ¦cru.obj ¦cru.c ¦Создание уникального файла ¦ ¦str_ut.obj ¦str_ut.c ¦Строковые функции ¦ ¦Wld.obj ¦Wld.c ¦Функции обработки DOS шаблона¦ ¦ci.obj ¦ci.c ¦Кол-во ITEM в (Под)индексе ¦ +-----------+----------------------------+-----------------------------+ ¦f_lxmul.obj¦ ¦Сервисные функции из стандар-¦ ¦h_ldiv.obj ¦ ¦тной библиотеки С. ¦ ¦h_llsh.obj ¦ ¦ ¦ ¦h_lursh.obj¦ ¦ ¦ L-----------+----------------------------+------------------------------ (таб.1) Сдесь Вы найдете примеры реализации алгоритмов обхода В-дерева (практически любой исходник, взаимодействующей с индексным файлом кроме FNtc.c), построение индекса методом "Сквозной массив" (SubNtx.c), построение индекса методом деления страниц по предпоследнему элементу (SbNtx.c), построение индекса по базе методом деления страниц пополам с сортировкой и предварительной сортировкой буфера ключей (FNtx.c). Я более менее детально опишу функцию SubNtx так как счетаю ее наиболее полезной в библиотеке. 4.1 SubNtx Из под CLIPPER функция вызывается так: SubNtx(, ; , ; [] , ; [], ; [/]) -> ErrCode - Строковая переменная с названием основного индекса.; - Строковая переменная с названием подиндекса.; [] - Верхняя граница ключей.; [] - Нижняя граница ключей.; [] - Блок кода. Блоку кода в качестве параметров передается индексный ключ и номер записи в базе данных. Блок должен возвращать логическое значение определяющее попадет ли данный ключ в подиндекс.; [] - Шаблон.; ErrCode - Признак завершение.; 0 - Успешное завершение.; 1 - Не правильно переданны параметры.; 2 - Не могу создать подиндекс.; 3 - Не могу открыть основной индекс.; 4 - Не могу заблокировать основной индекс.; 5 - Указанный файл по видимому не индексный файл драйвера DBFNTX.; 6 - Ошибка записи на диск.; 7 - Ошибка чтения с диска.; 8 - Ошибка выделения памяти. Работает она следующем образом. Первым делом проверяются параметры, открываются и блокируются все файлы, необходимые для работы. Затем инициализируется первая страница подиндекса и запускается рекурсивный проход по основному индексу процедурой pass_page( ntx_header.root ), начиная с корневой страницы. Эта процедура последовательно выдает уже сортированные ключи из основного индекса, удовлетворяющие всем необходимым условиям. Эти ключи передаются в процедуру реализующую медод "Сквозной массив" - AddItem(item). Сама функция AddItem() находиться в исходном тексте SubUt.c вместе с другими, необходимыми для работы процедурами. По завершении работы рекурсии программа увязывает страницы, оставшиеся в сквозном массиве методом Link_Rest(). Но это еще не все, хотя то, что мы получили есть полноценное В-дерево. Дело в том что драйвер DBFNTX отрабатывает конец файла только тогда, когда последний ITEM находиться на конечной странице, т.е. без ссылок на дочерние страница. Ситуация, когда конечный ITEM торчит на страницах более высокого уровня встречается редко, но встречается, и когда это происходит приходиться двигать последний ITEM с предпоследний конечной страницы. Этим занимаются функции: Make_BOF(), GoThare(long page_off), GoLeft(long page_off). На этом работа завершается. Пример использования функции SubNtx в CLIPPER находится в исходном тексте SUBIND.PRG и он тревиален. Просто вызывается функция SubNtx с переданным параметром наименования входного индекса, которая формирует другой индекс. В него переносятся все ключи из входного. Если Вы в качестве параметра укажете разрешенный индекс, то на выходе получите плотноупакованный. Объясняется это особенностью работы алгоритма "Сквозной массив". 5. Использование B-дерева в сжатии информации Благодаря уникальным особенностям В-деревьев они могут применяться везде, где требуется найти нечто в огромном объеме информации. Задачи подобного рода, как показала практика, требуют наибольших временных затрат и наиболее встречаемы в програмировании. В этом разделе я попытаюсь показать как можно "ускорить" алгоритм упаковки информации LZ. Работа алгоритма LZ основана на поиске повторных вхождений в сжимаемое сообщение некоторых строк и замены этих строк на ссылки первых вхождений. Если решать поставленную задачу "в лоб", то paker можно построить на функции сравнения строк: char StrCompWN(unsigned char * Str1, ; unsigned char * Str2, ; unsigned int uiN, ; unsigned int * uipN). В нее передаются сравниваемые строки, их длинна и указатель на некотурую величину, в которой потом возвращается число совпавших символов. Возвращает функция знаковое однобайтовое целое: -1 - меньше; 0 - равно; 1 - больше. Мы пробегаем все сообщение при этом пытаясь найти в уже просмотренном сообщение текущую строку, длинной не более установленной константы. Точнее мы ищем в уже просмотренном сообщении максимальное количество совпавших символов с текущей строкой, и если такое найдено, то выдаем в выходной поток ссылку на то, что нашли. В директории LZ0 Вы найдете программу, которая производит вышеотмеченный поиск простым перебором всех вариантов в цикле. Эта рабочая программа, она вполне серьезно пакует файлы, но беда в том, что работать она может годы на мало мальски серьезных файлах. Есть пара вариантов значительно лучше этого. Они находятся ссответственно в директориях LZ1 и LZ2 и отличаются от первого варианта тем, что создают для своей работы В-дерево в котором и производят поиск. Оба используют двух-уровневое дерево с разными страницами на уровнях. Такое тоже возможно и даже очень успешно. Оба хранят в В-дереве указатели на буфер входного сообщения. LZ1 производит интерактивную сортировку дерева методом половинного деления пробегая по сжимаемому буферу. Перед тем как добавить очередной указатель в индекс он патается его просто найти и если поиск удачный выдает в выходной поток ссылку. LZ2 сортирует дерево непосредственно перед алгоритмом кодирования входного буфера методом деления страниц предпоследним элементом, пробегая входное сообщение 256 раз. Работает это как ни странно бысрее вырианта LZ1. Поддержка В-дерева в обеих случаях происходит в исходном тексте btree.c. Этот файл содержит все необходимые функции сортировки и поиска ключей. На последок отмечу, что и описанные два алгоритма LZ1 и LZ2, не являются примером в быстродействии. Если Вы хотите получить конкурентноспособный по скорости и по степени сжатия паковщик Вам нужно предпринять следующее: 1) Использовать четырехуровневое дерево,; 2) Пересмотреть алгоритм перегрузки страниц,; 3) Попытаться совместить поиск с добавлением ключа для LZ1,; 4) Паковщик LZ выдает в выходной поток три категории различной информации: 1 - Не упакованные символы,; 2 - Длины,; 3 - Ссылки. Надо попытаться запаковать все три категории кодером не LZ, например алгоритмом Хафмена или арифметическим перекодированием, причем каждую категорию по отдельности. Успехов, господа! 6. Заключение Наверное, это все, что я имел сказать по данному вопрсу. Может быть чегото, правда, и забыл. Но это наверняка какие нибудь мелочи на которых не стоит заострять внимание. Наверное можно было догадаться, что меня весьма интересует данныя тема. Поэтому большая просьба ко всем, кто имеет в распоряжение нечто, мне неизвестное поделиться тем, что он имеет, например так, как это сделал я. Заранее спасибо! 1996 г. Карпов Владислав (095)450-30-51